#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <string>
#include <unordered_map>
using namespace std;
#define int long long


//void solve() {
//	int n, m, k;
//	cin >> n >> m >> k;
//	if (max(n - m, m - n) > k) {
//		cout << "-1\n";
//		return;
//	}
//	if (k > max(n, m)) {
//		cout << "-1\n";
//		return;
//	}
//	string ans;
//	if (n >= m) {
//		for (int i = 1; i <= k; i++) {
//			ans += '0';
//			n--;
//		}
//		while (n--) {
//			ans += "10";
//			m--;
//		}
//		while (m--)
//			ans += '1';
//	}
//	else {
//		for (int i = 1; i <= k; i++) {
//			ans += '1';
//			m--;
//		}
//		while (m--) {
//			ans += "01";
//			n--;
//		}
//		while (n--)
//			ans += '0';
//	}
//	cout<<ans<<'\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}

//void solve() {
//	int x, y;
//	cin >> x >> y;
//	if (x == y) {
//		cout << "-1\n";
//		return;
//	}
//	if (x < y)
//		swap(x, y);
//	int tmp = x;
//	int k = 0;
//	for (int i = 33; i >= 0; i--) {
//		if (x & (1ll << i)) {
//			k = (1ll << (i + 1)) - x;
//			break;
//		}
//	}
//	cout << k << '\n';
//}

//int d[200005];
//void solve() {
//	int n,k;
//	cin >> n >> k;
//	
//	priority_queue<int> q;
//	for (int i = 1; i <= n; i++) {
//		cin >> d[i];
//	}
//	int ans = 0;
//	for (int i = 1; i <= n - k; i++) {
//		q.push(d[i]);
//		if ((n - i + 1) % (k + 1) == 0) {
//			ans += q.top();
//			q.pop();
//		}
//	}
//	cout << ans << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}
//struct Table {
//    int a, b, sum;
//    Table(int a, int b) : a(a), b(b) {
//        sum = 3 * (a + b) + 2;
//    }
//    bool operator>(const Table& other) const {
//        if (sum != other.sum) return sum > other.sum;
//        if (a != other.a) return a > other.a;
//        return b > other.b;
//    }
//};
//
//void solve() {
//    int n;
//    cin >> n;
//    vector<int> t(n);
//    for (int i = 0; i < n; i++) {
//        cin >> t[i];
//    }
//
//    priority_queue<Table, vector<Table>, greater<Table>> available_unoccupied, available_partial;
//    unordered_map<int, unordered_map<int, int>> k_map;
//    int current_sum = 0;
//    int current_a = 0;
//    available_unoccupied.push(Table(0, 0));
//
//    auto generate_next = [&]() {
//        current_a++;
//        if (current_a > current_sum) {
//            current_sum++;
//            current_a = 0;
//        }
//        int new_a = current_a;
//        int new_b = current_sum - new_a;
//        available_unoccupied.push(Table(new_a, new_b));
//        };
//
//    generate_next();
//
//    for (int ti : t) {
//        if (ti == 0) {
//            while (true) {
//                if (available_unoccupied.empty()) {
//                    generate_next();
//                }
//                Table t = available_unoccupied.top();
//                available_unoccupied.pop();
//                int a = t.a, b = t.b;
//                if (k_map[a].count(b) == 0 || k_map[a][b] == 0) {
//                    k_map[a][b] = 1;
//                    int x = 3 * a + 1;
//                    int y = 3 * b + 1;
//                    cout << x << " " << y << endl;
//                    available_partial.push(t);
//                    generate_next();
//                    break;
//                }
//            }
//        }
//        else {
//            Table best_t(-1, -1);
//            bool found = false;
//            while (!found) {
//                Table unoc_t(-1, -1);
//                bool unoc_valid = false;
//                while (!available_unoccupied.empty()) {
//                    unoc_t = available_unoccupied.top();
//                    int a = unoc_t.a, b = unoc_t.b;
//                    if (k_map[a].count(b) == 0 || k_map[a][b] == 0) {
//                        unoc_valid = true;
//                        break;
//                    }
//                    else {
//                        available_unoccupied.pop();
//                    }
//                }
//                if (!unoc_valid) unoc_t = Table(-1, -1);
//
//                Table part_t(-1, -1);
//                bool part_valid = false;
//                while (!available_partial.empty()) {
//                    part_t = available_partial.top();
//                    int a = part_t.a, b = part_t.b;
//                    if (k_map[a].count(b) && k_map[a][b] >= 1 && k_map[a][b] < 4) {
//                        part_valid = true;
//                        break;
//                    }
//                    else {
//                        available_partial.pop();
//                    }
//                }
//                if (!part_valid) part_t = Table(-1, -1);
//
//                if (unoc_valid && part_valid) {
//                    if (unoc_t.sum < part_t.sum || (unoc_t.sum == part_t.sum && (unoc_t.a < part_t.a || (unoc_t.a == part_t.a && unoc_t.b < part_t.b)))) {
//                        best_t = unoc_t;
//                        available_partial.push(part_t);
//                    }
//                    else {
//                        best_t = part_t;
//                        if (unoc_valid) {
//                            available_unoccupied.push(unoc_t);
//                        }
//                    }
//                    found = true;
//                }
//                else if (unoc_valid) {
//                    best_t = unoc_t;
//                    found = true;
//                }
//                else if (part_valid) {
//                    best_t = part_t;
//                    found = true;
//                }
//                else {
//                    generate_next();
//                    available_unoccupied.push(Table(current_a, current_sum - current_a));
//                }
//            }
//
//            int a = best_t.a, b = best_t.b;
//            int k = k_map[a][b];
//            k_map[a][b]++;
//            int x, y;
//            switch (k) {
//            case 0:
//                x = 3 * a + 1;
//                y = 3 * b + 1;
//                available_partial.push(best_t);
//                break;
//            case 1:
//                x = 3 * a + 1;
//                y = 3 * b + 2;
//                break;
//            case 2:
//                x = 3 * a + 2;
//                y = 3 * b + 1;
//                break;
//            case 3:
//                x = 3 * a + 2;
//                y = 3 * b + 2;
//                break;
//            default:
//                x = y = -1;
//            }
//            cout << x << " " << y << endl;
//            if (k == 0) {
//                generate_next();
//            }
//            else if (k < 3) {
//                available_partial.push(best_t);
//            }
//        }
//    }
//}


//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}

//void solve() {
//	int x, y, a;
//	cin >> x >> y >> a;
//	int tmp = a % (x + y);
//	if (!tmp || tmp < x)
//		cout << "NO\n";
//	else
//		cout << "YES\n";
//}
//int grid[55][55];
//bool ok[55][55];
//
//
//
//bool up(int x, int y) {
//	if (!grid[x][y])
//		return false;
//	if (y <= 1)
//		return true;
//	if (up(x, y - 1)) {
//		ok[x][y] = 1;
//		return 1;
//	}
//	else
//		return false;
//}
//
//bool left(int x, int y) {
//	if (!grid[x][y])
//		return false;
//	if (x <= 1)
//		return true;
//	if (left(x - 1, y)) {
//		ok[x][y] = 1;
//		return 1;
//	}
//	else
//		return false;
//}
//
//void solve() {
//	int n, m;
//	cin >> n >> m;
//	deque<int> q;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			char ch;
//			cin >> ch;
//			grid[i][j] = ch - '0';
//			ok[i][j] = false;
//			if (grid[i][j]) {
//				q.push_back(i);
//				q.push_back(j);
//			}
//		}
//	}
//	while (!q.empty()) {
//		int y = q.back(); q.pop_back();
//		int x = q.back(); q.pop_back();
//		if (ok[x][y])
//			continue;
//		else if (up(x, y) || left(x, y)) {
//			continue;
//		}
//		else {
//			cout << "NO\n";
//			return;
//		}
//
//	}
//	cout << "YES\n";
//
//}

//int d[200005];
//void solve() {
//	int n, k;
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++)
//		cin >> d[i];
//	vector<int> dp(n + k + 1);
//	int j = 1;
//	for (int i = n - k; i >= 1; i--) {
//		dp[i] = max(dp[i + 1], dp[i + k + 1] + d[i]);
//		if (i < n - j * k) {
//			dp[i]=max(dp[])
//		}
//	}
//	cout << dp[1] << '\n';
//}
//
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//
//	return 0;
//}

//
//int a[5005];
//void solve() {
//	int n;
//	cin >> n;
//	bool all_zero = true;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		if (a[i])
//			all_zero = false;
//	}
//	if (all_zero) {
//		cout << "3\n";
//		cout << n - 1 << ' ' << n << '\n';
//		cout << 1 << ' ' << n - 2 << '\n';
//		cout << 1 << ' ' << 2 << '\n';
//		return;
//	}
//	int k = 0;
//	vector<int> ans;
//	int final = n;
//	for (int i = n; i >= 2; i--) {
//		if (a[i] == 0) {
//			int l = i - 1;
//			if (a[l] == 0) {
//				while (a[l] == 0 && l >= 1)
//					l--;
//				l++;
//			}
//			k++;
//			ans.push_back(l);
//			ans.push_back(i);
//			final -= i - l;
//			i = l;
//		}
//	}
//	if (a[1] == 0 && a[2] != 0) {
//		k++;
//		ans.push_back(1);
//		ans.push_back(2);
//		final--;
//	}
//	cout << k + 1 << '\n';
//	for (int i = 0; k; i += 2, k--) {
//		cout << ans[i] << ' ' << ans[i + 1] << '\n';
//	}
//	cout << 1 << ' ' << final << '\n';
//}
//void solve() {
//	int n, k;
//	string s;
//	cin >> n >> k >> s;
//	if (n == 1) {
//		cout << "NO\n";
//		return;
//	}
//	string res = s;
//	set<char> st(s.begin(), s.end());
//	reverse(res.begin(), res.end());
//
//	if (res == s && st.size() == 1) {
//		cout << "NO\n";
//	}
//	else if (s >= res && !k) {
//		cout << "NO\n";
//	}
//	else {
//		cout << "YES\n";
//	}
//}
//#define int long long
//vector<int> e[200005];
//int in[200005], chu[200005];
//queue<int> q;
//bool vis[200005];
//vector<int> ans;
//struct node
//{
//	int index, chu;
//	bool operator<(const node& x)const {
//		return chu < x.chu;
//	}
//};
//void dfs(int u, int fa) {
//	vis[u] = 1;
//	ans.push_back(u);
//	for (auto v : e[u]) {
//		if (v != fa && !vis[v])
//			dfs(v, u);
//	}
//}
//void solve() {
//	int n, m;
//	cin >> n >> m;
//	for (int i = 1, u, v; i <= m; i++) {
//		vis[i] = 0;
//		cin >> u >> v;
//		e[u].push_back(v);
//		in[v]++;
//		chu[u]++;
//	}
//	ans.clear();
//	for (int i = 1; i <= n; i++) {
//		if (!in[i]) {
//			q.push(i);
//			ans.push_back(i);
//			vis[i] = 1;
//		}
//	}
//	while (!q.empty()) {
//		int u = q.front();
//		q.pop();
//		for (auto v : e[u]) {
//			in[v]--;
//			if (!in[v]) {
//				q.push(v);
//				ans.push_back(v);
//				vis[v] = 1;
//			}
//		}
//	}
//	priority_queue<node> pq;
//	for (int i = 1; i <= n; i++) {
//		if (!vis[i])
//			pq.push({ i,chu[i] });
//	}
//	while (!pq.empty()) {
//		auto tmp = pq.top();
//		pq.pop();
//		if (vis[tmp.index])continue;
//		vis[tmp.index] = 1;
//		ans.push_back(tmp.index);
//		for (auto v : e[tmp.index]) {
//			if (!vis[v])
//				dfs(v, tmp.index);
//		}
//	}
//	for (int i = 0; i < n; i++) {
//		cout << ans[i] << ' ';
//		in[i] = 0;
//		chu[i] = 0;
//		e[i].clear();
//	}
//	cout << '\n';
//}
//
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int q;
//	cin >> q;
//	while (q--) {
//		solve();
//	}
//	return 0;
//}
